#include<cstdio>//uncle-lu
#include<cstring>
#include<queue>
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

void add_edge(int, int, int);
void spfa(void);

struct node{
	int v, next, val;
};
node edge[6000010];
int head[300010], cnt;
int line[100010];
int d[300010];
bool visit[300010];
int n, m;

void add_edge(int x, int y, int val)
{
	edge[++cnt].v = y;
	edge[cnt].val = val;
	edge[cnt].next = head[x];
	head[x] = cnt;
	return ;
}

void spfa()
{
	for(int i=1;i<=3*n+1;++i)
		d[i] = -0x7f7f7f7f;
	d[1] = 0;
	visit[1] = true;
	std::queue<int>qu;
	qu.push(1);
	while(!qu.empty())
	{
		int now = qu.front();
		qu.pop();
		visit[now] = false;
		for(int i=head[now];~i;i=edge[i].next)
		{
			if(d[edge[i].v] < d[now] + edge[i].val)
			{
				d[edge[i].v] = d[now] + edge[i].val;
				if(!visit[edge[i].v])
				{
					visit[edge[i].v] = true;
					qu.push(edge[i].v);
				}
			}
		}
	}
	return ;
}

int main()
{
	memset(head,-1,sizeof(head));

	int x, y, model;
	read(n);read(m);
	for(int i=1;i<=n;++i)
		read(line[i]);

	for(int i=1;i<=m;++i)
	{
		read(x); read(y); read(model);
		if(model == 1)
		{
			add_edge(x, y, 0);
			add_edge(x, y+n, -line[x]);
			add_edge(x+n, y+n, 0);
			add_edge(x+n, y+2*n, line[x]);
			add_edge(x+2*n, y+2*n, 0);
		}
		else
		{
			add_edge(x, y, 0); add_edge(y, x, 0);
			add_edge(x, y+n, -line[x]); add_edge(y, x+n, -line[y]);
			add_edge(x+n, y+n, 0); add_edge(y+n, x+n, 0);
			add_edge(x+n, y+2*n, line[x]); add_edge(y+n, x+2*n, line[y]);
			add_edge(x+2*n, y+2*n, 0); add_edge(y+2*n, x+2*n, 0);
		}
	}

	add_edge(n, 3*n+1, 0);
	add_edge(3*n, 3*n+1, 0);

	spfa();

	printf("%d",d[3*n+1]);

	return 0;
}
